<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>2462. 雇佣 K 位工人的总代价</title>
  </head>

  <body>
    https://leetcode.cn/problems/total-cost-to-hire-k-workers/description/?envType=daily-question&envId=2024-05-01
  </body>

  <script>
    function swap(arr, i, j) {
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }

    class MinHeap {
      constructor() {
        this.heap = [];
      }

      getLeftIndex(index) {
        return index * 2 + 1;
      }

      getRightIndex(index) {
        return index * 2 + 2;
      }

      getParentIndex(index) {
        if (index === 0) return undefined;
        return Math.floor((index - 1) / 2);
      }

      insert(val) {
        if (val !== null) {
          this.heap.push(val);
          this.shiftUp(this.heap.length - 1);
          return true;
        }

        return false;
      }

      shiftUp(index) {
        let parentIndex = this.getParentIndex(index);
        while (index > 0 && this.heap[parentIndex] > this.heap[index]) {
          swap(this.heap, parentIndex, index);
          index = parentIndex;
          parentIndex = this.getParentIndex(index);
        }
      }

      size() {
        return this.heap.length;
      }

      isEmpty() {
        return this.size() === 0;
      }

      findMinimum() {
        return this.isEmpty() ? undefined : this.heap[0];
      }

      getMinimum() {
        if (this.isEmpty()) return undefined;

        if (this.size() === 1) return this.heap.shift();

        const min = this.heap.shift();
        this.shiftDown(0);
        return min;
      }

      shiftDown(index) {
        let element = index;
        let leftIndex = this.getLeftIndex(index);
        let rightIndex = this.getRightIndex(index);

        let size = this.size();

        if (leftIndex < size && this.heap[element] >= this.heap[leftIndex]) {
          index = leftIndex;
        }

        if (rightIndex < size && this.heap[element] >= this.heap[rightIndex]) {
          index = rightIndex;
        }

        if (index !== element) {
          swap(this.heap, element, index);
          this.shiftDown(index);
        }
      }
    }
    /**
     * @param {number[]} costs
     * @param {number} k
     * @param {number} candidates
     * @return {number}
     */
    var totalCost = function (costs, k, candidates) {
      let total = 0;

      let findIndex = null;

      let endList = null;
      let startList = null;

      let costsHeap = null;

      if (costs.length > candidates * 2) {
        endList = new MinHeap();
        costs.splice(costs.length - candidates, costs.length).map((item) => {
          endList.insert(item);
        });

        startList = new MinHeap();
        costs.splice(0, candidates).map((item) => {
          startList.insert(item);
        });
      } else {
        costsHeap = new MinHeap();
        costs.map((item) => {
          costsHeap.insert(item);
        });
      }

      for (i = 0; i < k; i++) {
        // if (i === 7) debugger
        debugger;
        if (endList && startList) {
          let startMin = startList.findMinimum();
          let endMin = endList.findMinimum();

          if (startMin <= endMin) {
            findVal = startList.getMinimum();
            if (costs && costs.length) startList.insert(costs.shift());
          } else {
            findVal = endList.getMinimum();
            if (costs && costs.length) endList.insert(costs.pop());
          }

          if (!costs.length) {
            (endList.heap || []).map((item) => {
              startList.insert(item);
            });

            costsHeap = startList;

            startList = null;
            endList = null;
          }
        } else {
          if (costsHeap.size() === 0) return total;
          findVal = costsHeap.getMinimum();
        }

        total += findVal;
      }

      return total;
    };

    // let res = totalCost([17, 12, 10, 2, 7, 2, 11, 20, 8], 3, 4);
    // let res = totalCost([2, 2, 2, 2, 1, 2, 2, 2, 2], 9, 2);
    // let res = totalCost([31, 25, 72, 79, 74, 65, 84, 91, 18, 59, 27, 9, 81, 33, 17, 58], 11, 2);
    // let res = totalCost([
    // 	28, 35, 21, 13, 21, 72, 35, 52, 74, 92, 25, 65,
    // 	77, 1, 73, 32, 43, 68, 8, 100, 84, 80, 14, 88, 42, 53,
    // 	98, 69, 64, 40, 60, 23, 99, 83, 5, 21, 76, 34]
    // 	, 8, 12);
    // console.log(res)

    const testArr = [28, 35, 21, 13, 21, 72, 35, 52, 74, 92, 25, 65];
    const testHeap = new MinHeap();
    testArr.map((item) => {
      testHeap.insert(item);
    });

    for (i = 0; i < testHeap.size(); i++) {
      debugger;
      console.log(testHeap.getMinimum());
    }
  </script>
</html>
